1
2
3
4
5
6
7 package io.vavr.collection;
8
9 import io.vavr.Function1;
10 import io.vavr.PartialFunction;
11 import io.vavr.Tuple3;
12 import io.vavr.Tuple2;
13 import io.vavr.control.Option;
14
15 import java.io.Serializable;
16 import java.util.ArrayList;
17 import java.util.Comparator;
18 import java.util.NoSuchElementException;
19 import java.util.Objects;
20 import java.util.function.*;
21 import java.util.stream.Collector;
22
23
24
25
26
27
28 public interface BitSet<T> extends SortedSet<T> {
29
30 long serialVersionUID = 1L;
31
32 class Builder<T> {
33
34 final static Builder<Integer> DEFAULT = new Builder<>(i -> i, i -> i);
35
36 final Function1<Integer, T> fromInt;
37 final Function1<T, Integer> toInt;
38
39 Builder(Function1<Integer, T> fromInt, Function1<T, Integer> toInt) {
40 this.fromInt = fromInt;
41 this.toInt = toInt;
42 }
43
44 public Collector<T, ArrayList<T>, BitSet<T>> collector() {
45 final BinaryOperator<ArrayList<T>> combiner = (left, right) -> {
46 left.addAll(right);
47 return left;
48 };
49 return Collector.of(ArrayList::new, ArrayList::add, combiner, this::ofAll);
50 }
51
52 public BitSet<T> empty() {
53 return new BitSetModule.BitSet1<>(fromInt, toInt, 0L);
54 }
55
56 public BitSet<T> of(T t) {
57 final int value = toInt.apply(t);
58 if (value < BitSetModule.BITS_PER_WORD) {
59 return new BitSetModule.BitSet1<>(fromInt, toInt, 1L << value);
60 } else if (value < 2 * BitSetModule.BITS_PER_WORD) {
61 return new BitSetModule.BitSet2<>(fromInt, toInt, 0L, 1L << value);
62 } else {
63 return empty().add(t);
64 }
65 }
66
67 @SuppressWarnings("varargs")
68 @SafeVarargs
69 public final BitSet<T> of(T... values) {
70 return empty().addAll(Array.wrap(values));
71 }
72
73 public BitSet<T> ofAll(Iterable<? extends T> values) {
74 Objects.requireNonNull(values, "values is null");
75 return empty().addAll(values);
76 }
77
78 public BitSet<T> ofAll(java.util.stream.Stream<? extends T> javaStream) {
79 Objects.requireNonNull(javaStream, "javaStream is null");
80 return empty().addAll(Iterator.ofAll(javaStream.iterator()));
81 }
82
83 public BitSet<T> tabulate(int n, Function<? super Integer, ? extends T> f) {
84 Objects.requireNonNull(f, "f is null");
85 return empty().addAll(Collections.tabulate(n, f));
86 }
87
88 public BitSet<T> fill(int n, Supplier<? extends T> s) {
89 Objects.requireNonNull(s, "s is null");
90 return empty().addAll(Collections.fill(n, s));
91 }
92 }
93
94 static <T> Builder<T> withRelations(Function1<Integer, T> fromInt, Function1<T, Integer> toInt) {
95 return new Builder<>(fromInt, toInt);
96 }
97
98 @SuppressWarnings("RedundantTypeArguments")
99 static <T extends Enum<T>> Builder<T> withEnum(Class<T> enumClass) {
100 return new Builder<>(i -> enumClass.getEnumConstants()[i], Enum<T>::ordinal);
101 }
102
103 static Builder<Character> withCharacters() {
104 return new Builder<>(i -> (char) i.intValue(), c -> (int) c);
105 }
106
107 static Builder<Byte> withBytes() {
108 return new Builder<>(Integer::byteValue, Byte::intValue);
109 }
110
111 static Builder<Long> withLongs() {
112 return new Builder<>(Integer::longValue, Long::intValue);
113 }
114
115 static Builder<Short> withShorts() {
116 return new Builder<>(Integer::shortValue, Short::intValue);
117 }
118
119
120
121
122
123
124
125 static Collector<Integer, ArrayList<Integer>, BitSet<Integer>> collector() {
126 return Builder.DEFAULT.collector();
127 }
128
129 static BitSet<Integer> empty() {
130 return Builder.DEFAULT.empty();
131 }
132
133 static BitSet<Integer> of(Integer value) {
134 return Builder.DEFAULT.of(value);
135 }
136
137 static BitSet<Integer> of(Integer... values) {
138 return Builder.DEFAULT.of(values);
139 }
140
141
142
143
144
145
146
147
148
149
150 static BitSet<Integer> tabulate(int n, Function<Integer, Integer> f) {
151 return Builder.DEFAULT.tabulate(n, f);
152 }
153
154
155
156
157
158
159
160
161
162 static BitSet<Integer> fill(int n, Supplier<Integer> s) {
163 return Builder.DEFAULT.fill(n, s);
164 }
165
166 static BitSet<Integer> ofAll(Iterable<Integer> values) {
167 return Builder.DEFAULT.ofAll(values);
168 }
169
170 static BitSet<Integer> ofAll(java.util.stream.Stream<Integer> javaStream) {
171 return Builder.DEFAULT.ofAll(javaStream);
172 }
173
174
175
176
177
178
179
180
181 static BitSet<Boolean> ofAll(boolean... elements) {
182 Objects.requireNonNull(elements, "elements is null");
183 return BitSet.withRelations(i -> i != 0, b -> b ? 1 : 0).ofAll(Iterator.ofAll(elements));
184 }
185
186
187
188
189
190
191
192
193 static BitSet<Byte> ofAll(byte... elements) {
194 Objects.requireNonNull(elements, "elements is null");
195 return BitSet.withBytes().ofAll(Iterator.ofAll(elements));
196 }
197
198
199
200
201
202
203
204
205 static BitSet<Character> ofAll(char... elements) {
206 Objects.requireNonNull(elements, "elements is null");
207 return BitSet.withCharacters().ofAll(Iterator.ofAll(elements));
208 }
209
210
211
212
213
214
215
216
217 static BitSet<Integer> ofAll(int... elements) {
218 Objects.requireNonNull(elements, "elements is null");
219 return BitSet.ofAll(Iterator.ofAll(elements));
220 }
221
222
223
224
225
226
227
228
229 static BitSet<Long> ofAll(long... elements) {
230 Objects.requireNonNull(elements, "elements is null");
231 return BitSet.withLongs().ofAll(Iterator.ofAll(elements));
232 }
233
234
235
236
237
238
239
240
241 static BitSet<Short> ofAll(short... elements) {
242 Objects.requireNonNull(elements, "elements is null");
243 return BitSet.withShorts().ofAll(Iterator.ofAll(elements));
244 }
245
246
247
248
249
250
251
252
253 static BitSet<Integer> range(int from, int toExclusive) {
254 return BitSet.ofAll(Iterator.range(from, toExclusive));
255 }
256
257 static BitSet<Character> range(char from, char toExclusive) {
258 return BitSet.withCharacters().ofAll(Iterator.range(from, toExclusive));
259 }
260
261 static BitSet<Long> range(long from, long toExclusive) {
262 return BitSet.withLongs().ofAll(Iterator.range(from, toExclusive));
263 }
264
265
266
267
268
269
270
271
272
273
274
275
276
277 static BitSet<Integer> rangeBy(int from, int toExclusive, int step) {
278 return BitSet.ofAll(Iterator.rangeBy(from, toExclusive, step));
279 }
280
281 static BitSet<Character> rangeBy(char from, char toExclusive, int step) {
282 return BitSet.withCharacters().ofAll(Iterator.rangeBy(from, toExclusive, step));
283 }
284
285 static BitSet<Long> rangeBy(long from, long toExclusive, long step) {
286 return BitSet.withLongs().ofAll(Iterator.rangeBy(from, toExclusive, step));
287 }
288
289
290
291
292
293
294
295
296 static BitSet<Integer> rangeClosed(int from, int toInclusive) {
297 return BitSet.ofAll(Iterator.rangeClosed(from, toInclusive));
298 }
299
300 static BitSet<Character> rangeClosed(char from, char toInclusive) {
301 return BitSet.withCharacters().ofAll(Iterator.rangeClosed(from, toInclusive));
302 }
303
304 static BitSet<Long> rangeClosed(long from, long toInclusive) {
305 return BitSet.withLongs().ofAll(Iterator.rangeClosed(from, toInclusive));
306 }
307
308
309
310
311
312
313
314
315
316
317
318
319
320 static BitSet<Integer> rangeClosedBy(int from, int toInclusive, int step) {
321 return BitSet.ofAll(Iterator.rangeClosedBy(from, toInclusive, step));
322 }
323
324 static BitSet<Character> rangeClosedBy(char from, char toInclusive, int step) {
325 return BitSet.withCharacters().ofAll(Iterator.rangeClosedBy(from, toInclusive, step));
326 }
327
328 static BitSet<Long> rangeClosedBy(long from, long toInclusive, long step) {
329 return BitSet.withLongs().ofAll(Iterator.rangeClosedBy(from, toInclusive, step));
330 }
331
332 @Override
333 BitSet<T> add(T element);
334
335 @Override
336 BitSet<T> addAll(Iterable<? extends T> elements);
337
338 @Override
339 default <R> SortedSet<R> collect(PartialFunction<? super T, ? extends R> partialFunction) {
340 Objects.requireNonNull(partialFunction, "partialFunction is null");
341 return TreeSet.ofAll(Comparators.naturalComparator(), iterator().collect(partialFunction));
342 }
343
344 @Override
345 default BitSet<T> diff(Set<? extends T> elements) {
346 return removeAll(elements);
347 }
348
349 @Override
350 default BitSet<T> distinct() {
351 return this;
352 }
353
354 @Override
355 BitSet<T> distinctBy(Comparator<? super T> comparator);
356
357 @Override
358 <U> BitSet<T> distinctBy(Function<? super T, ? extends U> keyExtractor);
359
360 @Override
361 BitSet<T> drop(int n);
362
363 @Override
364 BitSet<T> dropRight(int n);
365
366 @Override
367 default BitSet<T> dropUntil(Predicate<? super T> predicate) {
368 Objects.requireNonNull(predicate, "predicate is null");
369 return dropWhile(predicate.negate());
370 }
371
372 @Override
373 BitSet<T> dropWhile(Predicate<? super T> predicate);
374
375 @Override
376 BitSet<T> filter(Predicate<? super T> predicate);
377
378 @Override
379 default <U> SortedSet<U> flatMap(Comparator<? super U> comparator, Function<? super T, ? extends Iterable<? extends U>> mapper) {
380 Objects.requireNonNull(mapper, "mapper is null");
381 return TreeSet.ofAll(comparator, iterator().flatMap(mapper));
382 }
383
384 @Override
385 default <U> SortedSet<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper) {
386 return flatMap(Comparators.naturalComparator(), mapper);
387 }
388
389 @Override
390 default <U> U foldRight(U zero, BiFunction<? super T, ? super U, ? extends U> f) {
391 Objects.requireNonNull(f, "f is null");
392 return iterator().foldRight(zero, f);
393 }
394
395 @Override
396 <C> Map<C, BitSet<T>> groupBy(Function<? super T, ? extends C> classifier);
397
398 @Override
399 default Iterator<BitSet<T>> grouped(int size) {
400 return sliding(size, size);
401 }
402
403 @Override
404 default boolean hasDefiniteSize() {
405 return true;
406 }
407
408 @Override
409 BitSet<T> init();
410
411 @Override
412 default Option<BitSet<T>> initOption() {
413 return isEmpty() ? Option.none() : Option.some(init());
414 }
415
416
417
418
419
420
421 @Override
422 default boolean isAsync() {
423 return false;
424 }
425
426 @Override
427 default boolean isTraversableAgain() {
428 return true;
429 }
430
431
432
433
434
435
436 @Override
437 default boolean isLazy() {
438 return false;
439 }
440
441 @Override
442 BitSet<T> intersect(Set<? extends T> elements);
443
444 @Override
445 Tuple2<BitSet<T>, BitSet<T>> partition(Predicate<? super T> predicate);
446
447 @Override
448 default BitSet<T> peek(Consumer<? super T> action) {
449 Objects.requireNonNull(action, "action is null");
450 if (!isEmpty()) {
451 action.accept(head());
452 }
453 return this;
454 }
455
456 @Override
457 default String stringPrefix() {
458 return "BitSet";
459 }
460
461 @Override
462 default <U> SortedSet<U> map(Comparator<? super U> comparator, Function<? super T, ? extends U> mapper) {
463 Objects.requireNonNull(mapper, "mapper is null");
464 return TreeSet.ofAll(comparator, iterator().map(mapper));
465 }
466
467 @Override
468 default <U> SortedSet<U> map(Function<? super T, ? extends U> mapper) {
469 return map(Comparators.naturalComparator(), mapper);
470 }
471
472 @Override
473 BitSet<T> remove(T element);
474
475 @Override
476 BitSet<T> removeAll(Iterable<? extends T> elements);
477
478 @Override
479 default BitSet<T> replace(T currentElement, T newElement) {
480 if (contains(currentElement)) {
481 return remove(currentElement).add(newElement);
482 } else {
483 return this;
484 }
485 }
486
487 @Override
488 default BitSet<T> replaceAll(T currentElement, T newElement) {
489
490 return replace(currentElement, newElement);
491 }
492
493 @Override
494 default BitSet<T> retainAll(Iterable<? extends T> elements) {
495 return Collections.retainAll(this, elements);
496 }
497
498 @Override
499 BitSet<T> scan(T zero, BiFunction<? super T, ? super T, ? extends T> operation);
500
501 @Override
502 default <U> Set<U> scanLeft(U zero, BiFunction<? super U, ? super T, ? extends U> operation) {
503 return Collections.scanLeft(this, zero, operation, HashSet::ofAll);
504 }
505
506 @Override
507 default <U> Set<U> scanRight(U zero, BiFunction<? super T, ? super U, ? extends U> operation) {
508 return Collections.scanRight(this, zero, operation, HashSet::ofAll);
509 }
510
511 @Override
512 Iterator<BitSet<T>> slideBy(Function<? super T, ?> classifier);
513
514 @Override
515 default Iterator<BitSet<T>> sliding(int size) {
516 return sliding(size, 1);
517 }
518
519 @Override
520 Iterator<BitSet<T>> sliding(int size, int step);
521
522 @Override
523 Tuple2<BitSet<T>, BitSet<T>> span(Predicate<? super T> predicate);
524
525 @Override
526 default BitSet<T> tail() {
527 if (isEmpty()) {
528 throw new UnsupportedOperationException("tail of empty BitSet");
529 } else {
530 return drop(1);
531 }
532 }
533
534 @Override
535 default Option<BitSet<T>> tailOption() {
536 return isEmpty() ? Option.none() : Option.some(tail());
537 }
538
539 @Override
540 BitSet<T> take(int n);
541
542 @Override
543 BitSet<T> takeRight(int n);
544
545 @Override
546 default BitSet<T> takeUntil(Predicate<? super T> predicate) {
547 Objects.requireNonNull(predicate, "predicate is null");
548 return takeWhile(predicate.negate());
549 }
550
551 @Override
552 BitSet<T> takeWhile(Predicate<? super T> predicate);
553
554 @Override
555 default java.util.SortedSet<T> toJavaSet() {
556 return toJavaSet(ignore -> new java.util.TreeSet<>(comparator()));
557 }
558
559 @Override
560 default BitSet<T> union(Set<? extends T> elements) {
561 Objects.requireNonNull(elements, "elements is null");
562 return elements.isEmpty() ? this : addAll(elements);
563 }
564
565 @Override
566 default <T1, T2> Tuple2<TreeSet<T1>, TreeSet<T2>> unzip(
567 Function<? super T, Tuple2<? extends T1, ? extends T2>> unzipper) {
568 Objects.requireNonNull(unzipper, "unzipper is null");
569 return iterator().unzip(unzipper).map(i1 -> TreeSet.ofAll(Comparators.naturalComparator(), i1),
570 i2 -> TreeSet.ofAll(Comparators.naturalComparator(), i2));
571 }
572
573 @Override
574 default <T1, T2, T3> Tuple3<TreeSet<T1>, TreeSet<T2>, TreeSet<T3>> unzip3(
575 Function<? super T, Tuple3<? extends T1, ? extends T2, ? extends T3>> unzipper) {
576 Objects.requireNonNull(unzipper, "unzipper is null");
577 return iterator().unzip3(unzipper).map(
578 i1 -> TreeSet.ofAll(Comparators.naturalComparator(), i1),
579 i2 -> TreeSet.ofAll(Comparators.naturalComparator(), i2),
580 i3 -> TreeSet.ofAll(Comparators.naturalComparator(), i3));
581 }
582
583 @Override
584 default <U> TreeSet<Tuple2<T, U>> zip(Iterable<? extends U> that) {
585 Objects.requireNonNull(that, "that is null");
586 final Comparator<Tuple2<T, U>> tuple2Comparator = Tuple2.comparator(comparator(), Comparators.naturalComparator());
587 return TreeSet.ofAll(tuple2Comparator, iterator().zip(that));
588 }
589
590 @Override
591 default <U, R> TreeSet<R> zipWith(Iterable<? extends U> that, BiFunction<? super T, ? super U, ? extends R> mapper) {
592 Objects.requireNonNull(that, "that is null");
593 Objects.requireNonNull(mapper, "mapper is null");
594 return TreeSet.ofAll(Comparators.naturalComparator(), iterator().zipWith(that, mapper));
595 }
596
597 @Override
598 default <U> TreeSet<Tuple2<T, U>> zipAll(Iterable<? extends U> that, T thisElem, U thatElem) {
599 Objects.requireNonNull(that, "that is null");
600 final Comparator<Tuple2<T, U>> tuple2Comparator = Tuple2.comparator(comparator(), Comparators.naturalComparator());
601 return TreeSet.ofAll(tuple2Comparator, iterator().zipAll(that, thisElem, thatElem));
602 }
603
604 @Override
605 default TreeSet<Tuple2<T, Integer>> zipWithIndex() {
606 final Comparator<? super T> component1Comparator = comparator();
607 final Comparator<Tuple2<T, Integer>> tuple2Comparator = (t1, t2) -> component1Comparator.compare(t1._1, t2._1);
608 return TreeSet.ofAll(tuple2Comparator, iterator().zipWithIndex());
609 }
610
611 @Override
612 default <U> TreeSet<U> zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U> mapper) {
613 Objects.requireNonNull(mapper, "mapper is null");
614 return TreeSet.ofAll(Comparators.naturalComparator(), iterator().zipWithIndex(mapper));
615 }
616 }
617
618 interface BitSetModule {
619
620 int ADDRESS_BITS_PER_WORD = 6;
621 int BITS_PER_WORD = 64;
622
623 abstract class AbstractBitSet<T> implements BitSet<T>, Serializable {
624
625 private static final long serialVersionUID = 1L;
626
627 final Function1<Integer, T> fromInt;
628 final Function1<T, Integer> toInt;
629
630 AbstractBitSet(Function1<Integer, T> fromInt, Function1<T, Integer> toInt) {
631 this.fromInt = fromInt;
632 this.toInt = toInt;
633 }
634
635 abstract int getWordsNum();
636
637 abstract long[] copyExpand(int wordsNum);
638
639 abstract long getWord(int index);
640
641 BitSet<T> createEmpty() {
642 return new BitSet1<>(fromInt, toInt, 0L);
643 }
644
645 @SuppressWarnings("unchecked")
646 BitSet<T> createFromAll(Iterable<? extends T> values) {
647 return values instanceof BitSet ? (BitSet<T>) values : createEmpty().addAll(values);
648 }
649
650 BitSet<T> fromBitMaskNoCopy(long[] elements) {
651 final int len = elements.length;
652 if (len == 0) {
653 return createEmpty();
654 } else if (len == 1) {
655 return new BitSet1<>(fromInt, toInt, elements[0]);
656 } else if (len == 2) {
657 return new BitSet2<>(fromInt, toInt, elements[0], elements[1]);
658 } else {
659 return new BitSetN<>(fromInt, toInt, elements);
660 }
661 }
662
663 private void setElement(long[] words, int element) {
664 final int index = element >> ADDRESS_BITS_PER_WORD;
665 words[index] |= (1L << element);
666 }
667
668 private void unsetElement(long[] words, int element) {
669 final int index = element >> ADDRESS_BITS_PER_WORD;
670 words[index] &= ~(1L << element);
671 }
672
673 long[] shrink(long[] elements) {
674 int newlen = elements.length;
675 while (newlen > 0 && elements[newlen - 1] == 0) {
676 newlen--;
677 }
678 final long[] newelems = new long[newlen];
679 System.arraycopy(elements, 0, newelems, 0, newlen);
680 return newelems;
681 }
682
683 BitSet<T> addElement(int element) {
684 final long[] copy = copyExpand(1 + (element >> ADDRESS_BITS_PER_WORD));
685 setElement(copy, element);
686 return fromBitMaskNoCopy(copy);
687 }
688
689 @Override
690 public BitSet<T> distinctBy(Comparator<? super T> comparator) {
691 Objects.requireNonNull(comparator, "comparator is null");
692 return isEmpty() ? this : createFromAll(iterator().distinctBy(comparator));
693 }
694
695 @Override
696 public <U> BitSet<T> distinctBy(Function<? super T, ? extends U> keyExtractor) {
697 Objects.requireNonNull(keyExtractor, "keyExtractor is null");
698 return isEmpty() ? this : createFromAll(iterator().distinctBy(keyExtractor));
699 }
700
701 @Override
702 public BitSet<T> drop(int n) {
703 if (n <= 0 || isEmpty()) {
704 return this;
705 } else if (n >= length()) {
706 return createEmpty();
707 } else {
708 return createFromAll(iterator().drop(n));
709 }
710 }
711
712 @Override
713 public BitSet<T> dropRight(int n) {
714 if (n <= 0 || isEmpty()) {
715 return this;
716 } else if (n >= length()) {
717 return createEmpty();
718 } else {
719 return createFromAll(iterator().dropRight(n));
720 }
721 }
722
723 @Override
724 public BitSet<T> dropWhile(Predicate<? super T> predicate) {
725 Objects.requireNonNull(predicate, "predicate is null");
726 final BitSet<T> bitSet = createFromAll(iterator().dropWhile(predicate));
727 return (bitSet.length() == length()) ? this : bitSet;
728 }
729
730 @Override
731 public BitSet<T> intersect(Set<? extends T> elements) {
732 Objects.requireNonNull(elements, "elements is null");
733 if (isEmpty()) {
734 return this;
735 } else if (elements.isEmpty()) {
736 return createEmpty();
737 } else {
738 final int size = size();
739 if (size <= elements.size()) {
740 return retainAll(elements);
741 } else {
742 final BitSet<T> results = createFromAll(elements).retainAll(this);
743 return (size == results.size()) ? this : results;
744 }
745 }
746 }
747
748
749
750
751
752
753
754
755
756 @Override
757 public BitSet<T> orElse(Iterable<? extends T> other) {
758 return isEmpty() ? createFromAll(other) : this;
759 }
760
761
762
763
764
765
766
767
768
769 @Override
770 public BitSet<T> orElse(Supplier<? extends Iterable<? extends T>> supplier) {
771 return isEmpty() ? createFromAll(supplier.get()) : this;
772 }
773
774 @Override
775 public Iterator<BitSet<T>> slideBy(Function<? super T, ?> classifier) {
776 return iterator().slideBy(classifier).map(this::createFromAll);
777 }
778
779 @Override
780 public Iterator<BitSet<T>> sliding(int size, int step) {
781 return iterator().sliding(size, step).map(this::createFromAll);
782 }
783
784 @Override
785 public Tuple2<BitSet<T>, BitSet<T>> span(Predicate<? super T> predicate) {
786 Objects.requireNonNull(predicate, "predicate is null");
787 return iterator().span(predicate).map(this::createFromAll, this::createFromAll);
788 }
789
790 @Override
791 public BitSet<T> scan(T zero, BiFunction<? super T, ? super T, ? extends T> operation) {
792 return Collections.scanLeft(this, zero, operation, this::createFromAll);
793 }
794
795 @Override
796 public Tuple2<BitSet<T>, BitSet<T>> partition(Predicate<? super T> predicate) {
797 Objects.requireNonNull(predicate, "predicate is null");
798 return iterator().partition(predicate).map(this::createFromAll, this::createFromAll);
799 }
800
801 @Override
802 public BitSet<T> filter(Predicate<? super T> predicate) {
803 Objects.requireNonNull(predicate, "predicate is null");
804 final BitSet<T> bitSet = createFromAll(iterator().filter(predicate));
805 return (bitSet.length() == length()) ? this : bitSet;
806 }
807
808 @Override
809 public <C> Map<C, BitSet<T>> groupBy(Function<? super T, ? extends C> classifier) {
810 return Collections.groupBy(this, classifier, this::createFromAll);
811 }
812
813 @Override
814 public Comparator<T> comparator() {
815 return Comparator.comparing(toInt);
816 }
817
818 @Override
819 public BitSet<T> takeWhile(Predicate<? super T> predicate) {
820 Objects.requireNonNull(predicate, "predicate is null");
821 final BitSet<T> result = createFromAll(iterator().takeWhile(predicate));
822 return (result.length() == length()) ? this : result;
823 }
824
825 @Override
826 @SuppressWarnings("unchecked")
827 public BitSet<T> addAll(Iterable<? extends T> elements) {
828 final Stream<Integer> source = Stream.ofAll(elements).map(toInt);
829 if (source.isEmpty()) {
830 return this;
831 } else {
832 final long[] copy = copyExpand(1 + (source.max().getOrElse(0) >> ADDRESS_BITS_PER_WORD));
833 source.forEach(element -> {
834 if (element < 0) {
835 throw new IllegalArgumentException("bitset element must be >= 0");
836 }
837 setElement(copy, element);
838 });
839 final BitSet<T> bitSet = fromBitMaskNoCopy(copy);
840 return (bitSet.length() == length()) ? this : bitSet;
841 }
842 }
843
844 @Override
845 public boolean contains(T t) {
846 final int element = toInt.apply(t);
847 if (element < 0) {
848 throw new IllegalArgumentException("bitset element must be >= 0");
849 }
850 final int index = element >> ADDRESS_BITS_PER_WORD;
851 return index < getWordsNum() && (getWord(index) & (1L << element)) != 0;
852 }
853
854 @Override
855 public BitSet<T> init() {
856 if (isEmpty()) {
857 throw new UnsupportedOperationException("init of empty TreeSet");
858 } else {
859 final long last = getWord(getWordsNum() - 1);
860 final int element = BITS_PER_WORD * (getWordsNum() - 1) + BITS_PER_WORD - Long.numberOfLeadingZeros(last) - 1;
861 return remove(fromInt.apply(element));
862 }
863 }
864
865 @Override
866 public Iterator<T> iterator() {
867 return new BitSetIterator<>(this);
868 }
869
870 @Override
871 public BitSet<T> take(int n) {
872 if (isEmpty() || n >= length()) {
873 return this;
874 } else if (n <= 0) {
875 return createEmpty();
876 } else {
877 return createFromAll(iterator().take(n));
878 }
879 }
880
881 @Override
882 public BitSet<T> takeRight(int n) {
883 if (isEmpty() || n >= length()) {
884 return this;
885 } else if (n <= 0) {
886 return createEmpty();
887 } else {
888 return createFromAll(iterator().takeRight(n));
889 }
890 }
891
892 @Override
893 public BitSet<T> remove(T t) {
894 if (contains(t)) {
895 final int element = toInt.apply(t);
896 final long[] copy = copyExpand(getWordsNum());
897 unsetElement(copy, element);
898 return fromBitMaskNoCopy(shrink(copy));
899 } else {
900 return this;
901 }
902 }
903
904 @Override
905 public BitSet<T> removeAll(Iterable<? extends T> elements) {
906 if (isEmpty()) {
907 return this;
908 } else {
909 final Stream<Integer> source = Stream.ofAll(elements).map(toInt);
910 if (source.isEmpty()) {
911 return this;
912 } else {
913 final long[] copy = copyExpand(getWordsNum());
914 source.forEach(element -> unsetElement(copy, element));
915 return fromBitMaskNoCopy(shrink(copy));
916 }
917 }
918 }
919
920 @Override
921 public String toString() {
922 return mkString(stringPrefix() + "(", ", ", ")");
923 }
924
925 @Override
926 public boolean equals(Object o) {
927 return Collections.equals(this, o);
928 }
929
930 @Override
931 public int hashCode() {
932 return Collections.hashUnordered(this);
933 }
934 }
935
936 class BitSetIterator<T> extends AbstractIterator<T> {
937
938 private final AbstractBitSet<T> bitSet;
939
940 private long element;
941 private int index;
942
943 BitSetIterator(AbstractBitSet<T> bitSet) {
944 this.bitSet = bitSet;
945 this.element = bitSet.getWord(0);
946 this.index = 0;
947 }
948
949 @Override
950 protected T getNext() {
951 final int pos = Long.numberOfTrailingZeros(element);
952 element &= ~(1L << pos);
953 return bitSet.fromInt.apply(pos + (index << ADDRESS_BITS_PER_WORD));
954 }
955
956 @Override
957 public boolean hasNext() {
958 if (element == 0) {
959 while (element == 0 && index < bitSet.getWordsNum() - 1) {
960 element = bitSet.getWord(++index);
961 }
962 return element != 0;
963 } else {
964 return true;
965 }
966 }
967 }
968
969 class BitSet1<T> extends AbstractBitSet<T> {
970
971 private static final long serialVersionUID = 1L;
972
973 private final long elements;
974 private final int len;
975
976 BitSet1(Function1<Integer, T> fromInt, Function1<T, Integer> toInt, long elements) {
977 super(fromInt, toInt);
978 this.elements = elements;
979 this.len = Long.bitCount(elements);
980 }
981
982 @Override
983 int getWordsNum() {
984 return 1;
985 }
986
987 @Override
988 long[] copyExpand(int wordsNum) {
989 if (wordsNum < 1) {
990 wordsNum = 1;
991 }
992 final long[] arr = new long[wordsNum];
993 arr[0] = elements;
994 return arr;
995 }
996
997 @Override
998 long getWord(int index) {
999 return elements;
1000 }
1001
1002 @Override
1003 public T head() {
1004 if (elements == 0) {
1005 throw new NoSuchElementException("head of empty BitSet");
1006 } else {
1007 return fromInt.apply(Long.numberOfTrailingZeros(elements));
1008 }
1009 }
1010
1011 @Override
1012 public int length() {
1013 return len;
1014 }
1015
1016 @Override
1017 public BitSet<T> add(T t) {
1018 final int element = toInt.apply(t);
1019 if (element < 0) {
1020 throw new IllegalArgumentException("bitset element must be >= 0");
1021 }
1022 if (element < BITS_PER_WORD) {
1023 final long mask = 1L << element;
1024 if ((elements & mask) != 0) {
1025 return this;
1026 } else {
1027 return new BitSet1<>(fromInt, toInt, elements | mask);
1028 }
1029 } else {
1030 return addElement(element);
1031 }
1032 }
1033 }
1034
1035 class BitSet2<T> extends AbstractBitSet<T> {
1036
1037 private static final long serialVersionUID = 1L;
1038
1039 private final long elements1, elements2;
1040 private final int len;
1041
1042 BitSet2(Function1<Integer, T> fromInt, Function1<T, Integer> toInt, long elements1, long elements2) {
1043 super(fromInt, toInt);
1044 this.elements1 = elements1;
1045 this.elements2 = elements2;
1046 this.len = Long.bitCount(elements1) + Long.bitCount(elements2);
1047 }
1048
1049 @Override
1050 int getWordsNum() {
1051 return 2;
1052 }
1053
1054 @Override
1055 long[] copyExpand(int wordsNum) {
1056 if (wordsNum < 2) {
1057 wordsNum = 2;
1058 }
1059 final long[] arr = new long[wordsNum];
1060 arr[0] = elements1;
1061 arr[1] = elements2;
1062 return arr;
1063 }
1064
1065 @Override
1066 long getWord(int index) {
1067 if (index == 0) {
1068 return elements1;
1069 } else {
1070 return elements2;
1071 }
1072 }
1073
1074 @Override
1075 public T head() {
1076 if (elements1 == 0) {
1077 return fromInt.apply(BITS_PER_WORD + Long.numberOfTrailingZeros(elements2));
1078 } else {
1079 return fromInt.apply(Long.numberOfTrailingZeros(elements1));
1080 }
1081 }
1082
1083 @Override
1084 public int length() {
1085 return len;
1086 }
1087
1088 @Override
1089 public BitSet<T> add(T t) {
1090 final int element = toInt.apply(t);
1091 if (element < 0) {
1092 throw new IllegalArgumentException("bitset element must be >= 0");
1093 }
1094 final long mask = 1L << element;
1095 if (element < BITS_PER_WORD) {
1096 if ((elements1 & mask) != 0) {
1097 return this;
1098 } else {
1099 return new BitSet2<>(fromInt, toInt, elements1 | mask, elements2);
1100 }
1101 } else if (element < 2 * BITS_PER_WORD) {
1102 if ((elements2 & mask) != 0) {
1103 return this;
1104 } else {
1105 return new BitSet2<>(fromInt, toInt, elements1, elements2 | mask);
1106 }
1107 } else {
1108 return addElement(element);
1109 }
1110 }
1111 }
1112
1113 class BitSetN<T> extends AbstractBitSet<T> {
1114
1115 private static final long serialVersionUID = 1L;
1116
1117 private final long[] elements;
1118 private final int len;
1119
1120 BitSetN(Function1<Integer, T> fromInt, Function1<T, Integer> toInt, long[] elements) {
1121 super(fromInt, toInt);
1122 this.elements = elements;
1123 this.len = calcLength(elements);
1124 }
1125
1126 private static int calcLength(long[] elements) {
1127 int len = 0;
1128 for (long element : elements) {
1129 len += Long.bitCount(element);
1130 }
1131 return len;
1132 }
1133
1134 @Override
1135 int getWordsNum() {
1136 return elements.length;
1137 }
1138
1139 @Override
1140 long[] copyExpand(int wordsNum) {
1141 if (wordsNum < elements.length) {
1142 wordsNum = elements.length;
1143 }
1144 final long[] arr = new long[wordsNum];
1145 System.arraycopy(elements, 0, arr, 0, elements.length);
1146 return arr;
1147 }
1148
1149 @Override
1150 long getWord(int index) {
1151 return elements[index];
1152 }
1153
1154 @Override
1155 public T head() {
1156 int offset = 0;
1157 int element = 0;
1158 for (int i = 0; i < getWordsNum(); i++) {
1159 if (elements[i] == 0) {
1160 offset += BITS_PER_WORD;
1161 } else {
1162 element = offset + Long.numberOfTrailingZeros(elements[i]);
1163 break;
1164 }
1165 }
1166 return fromInt.apply(element);
1167 }
1168
1169 @Override
1170 public int length() {
1171 return len;
1172 }
1173
1174 @Override
1175 public BitSet<T> add(T t) {
1176 if (contains(t)) {
1177 return this;
1178 } else {
1179 return addElement(toInt.apply(t));
1180 }
1181 }
1182 }
1183 }